package com.wwy.arithmetic.suanfa;


import com.wwy.arithmetic.suanfa.entry.TreeNode;
import lombok.Data;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 完全二叉树的节点个数
 */
public class TreeNodeNumber {
    @Data
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode() {
        }
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(5);
        TreeNode node5 = new TreeNode(6);
        node.left = node1;
        node.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        int i = countNodes(node);
        System.out.println("i = " + i);
    }

    /**
     * 1
     * 2  3
     * 4 5 6
     *
     * @param left
     * @param a
     * @return
     */
    static int countNodes(TreeNode left) {
        return left == null ? 0 : countNodes(left.left) + countNodes(left.right) + 1;
    }

    /**
     * 使用栈来解决
     *
     * @param root
     * @return
     */
    static int getStackNum(TreeNode root) {
        int a = 0;
        Deque<TreeNode> deque = new LinkedList<>();
        while (!deque.isEmpty() || root != null) {
            while (root != null) {
                a++;
                deque.push(root);
                root = root.left;
            }
            root = deque.pop();
            root = root.getRight();
        }
        return a;
    }
}
